34 栈的概念及实现(上)
栈的概念及实现
-
栈的定义
- 栈是一种特殊的线性表
- 栈仅能在线性表的一端进行操作
- 栈顶(Top):允许操作的一端
- 栈底(Bottom):不允许操作的一端
-
栈的特性
- 先进后出(Last In First Out)
-
栈的操作
- 创建栈( Stack() )
- 销毁栈( ~Stack() )
- 清空栈( clear() )
- 进栈( push() )
- 出栈( pop() )
- 获取栈顶元素( top() )
- 获取栈的大小( size() )
-
栈的实现
template<typename T>
class Stack : public Object
{
public:
virtual void push(const T &e) = 0;
virtual void pop() = 0;
virtual T top() const = 0;
virtual void clear() = 0;
virtual int size() const = 0;
}; -
栈的顺序实现
-
StaticStack设计要点- 类模板
- 使用原生数组作为栈的存储空间
- 使用模板参数决定栈的最大容量
template<typename T,int N>
class StaticStack : public Stack<T>
{
public:
StaticStack(); //初始化成员变量
int capacity() const;
//...
protected:
T m_space[N]; //栈存储空间，N为模板参数
int m_top; //栈顶标识
int m_size; //当前栈的大小
} - 类模板
编程实验
-
基于顺序存储结构的栈
小结
- 栈是一种特殊的线性表
- 栈只允许在线性表的一端进行操作
StaticStack使用原生数组作为内部存储空间StaticStack的最大容量有模板参数决定
35 栈的概念及实现(下)
栈的概念及实现
-
讨论中
A :
StaticStack是由缺陷的 B : 怎么可能!这是老师带着我们实现的哦| A : 当存储的元素为类类型时,StaticStack的对象在创建时,会多次调用元素类型的构造函数,影响效率。 B : 你胡说...... -
链式栈的存储实现
-
链式栈的设计要点
- 类模板，抽象父类Stack的直接子类
- 在内部组合使用
LinkedList类，实现栈的链式存储 - 只在单链表成员对象的头部进行操作
-
链式栈的设计要点
编程实验
-
基于链式存储结构的栈
栈的应用
-
栈的应用实践
-
符号匹配问题
-
在C语言中有一些成对匹配出现的符号
-
括号 : (),[ ],{ },< >
-
引号 : " ",' '
-
-
-
问题 如何实现编译器中的符号成对检测?
-
算法思路
-
从第一个字符开始扫描
- 当遇见普通字符时忽略
- 当遇见左符号时压入栈中
- 当遇见右符号时弹出栈顶符号,并进行匹配
-
结束
- 成功 : 所有字符扫描完毕，且栈为空
- 失败 : 匹配失败或所有字符扫描完毕但栈非空
-
编程实验
-
符号匹配问题
小结
- 链式栈的实现组合使用了单链表对象
- 在单链表的头部进行操作能够实现高效的入栈和出栈操作
- 栈"后进先出"的特性适用于检测成对出现的符号
- 栈非常适合于需要"就近匹配"的场合
深度思考
-
开放性问题 使用单链表对象实现链式栈时，为什么选择在单链表的头部进行操作?如果在尾部进行操作是否也能实现栈的功能?
头部操作，时间复杂度为O(1)，在尾部操作时时间复杂度为O(n)